Heavy- Light Decomposition Algorithm
The Heavy-Light Decomposition Algorithm is an advanced data structure technique used predominantly in solving complex problems related to trees in computer science. It works by dividing the original tree into a set of smaller, disjoint chains, which can be processed more efficiently. These chains, called heavy-light chains, are created based on the size of the subtrees, and are designed to ensure that the depth of the tree is minimized, thus reducing the complexity of the subsequent operations. The key idea behind this decomposition is that it allows us to perform various path and subtree queries in logarithmic time, enabling us to handle large trees and process numerous queries efficiently.
To achieve this efficient decomposition, the algorithm first identifies the "heavy" and "light" edges in the tree. A heavy edge is an edge that connects a node to its child with the largest subtree size, while a light edge connects the node to all its other children. The heavy-light chains are then formed by traversing the tree's heavy edges, and at every node that has a light edge, we start a new chain. This process ensures that each chain has a logarithmic length, significantly reducing the complexity of traversal and update operations. The heavy-light decomposition algorithm is versatile and can be combined with other data structures like segment trees, binary indexed trees, and range minimum query data structures to solve a wide range of complex tree-related problems in computer science.
/*
Petar 'PetarV' Velickovic
Algorithm: Heavy-Light Decomposition
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
#define MAX_N 1000001
#define INF 987654321
using namespace std;
typedef long long lld;
typedef unsigned long long llu;
/*
Heavy-Light Decomposition algorithm for partitioning the edges of a tree into two groups - heavy and light.
Can be used for efficient traversal from any node to the root of the tree, since there are at most log n light edges
along that path; hence, we can skip entire chains of heavy edges.
Complexity: O(n)
*/
struct Node
{
vector<int> adj;
};
Node graf[MAX_N];
struct TreeNode
{
int parent;
int depth;
int chainTop;
int subTreeSize;
};
TreeNode T[MAX_N];
int DFS(int root, int parent, int depth)
{
T[root].parent = parent;
T[root].depth = depth;
T[root].subTreeSize = 1;
for (int i=0;i<graf[root].adj.size();i++)
{
int xt = graf[root].adj[i];
if (xt == parent) continue;
T[root].subTreeSize += DFS(xt, root, depth+1);
}
return T[root].subTreeSize;
}
void HLD(int root, int parent, int chainTop)
{
T[root].chainTop = chainTop;
for (int i=0;i<graf[root].adj.size();i++)
{
int xt = graf[root].adj[i];
if (xt == parent) continue;
if (T[xt].subTreeSize*1.0 > T[root].subTreeSize*0.5) HLD(xt, root, chainTop);
else HLD(xt, root, xt);
}
}
inline int LCA(int u, int v)
{
while (T[u].chainTop != T[v].chainTop)
{
if (T[T[u].chainTop].depth < T[T[v].chainTop].depth) v = T[T[v].chainTop].parent;
else u = T[T[u].chainTop].parent;
}
if (T[u].depth < T[v].depth) return u;
else return v;
}
int n;
int main()
{
n = 7;
graf[1].adj.push_back(2);
graf[2].adj.push_back(1);
graf[1].adj.push_back(3);
graf[3].adj.push_back(1);
graf[1].adj.push_back(4);
graf[4].adj.push_back(1);
graf[3].adj.push_back(5);
graf[5].adj.push_back(3);
graf[3].adj.push_back(6);
graf[6].adj.push_back(3);
graf[3].adj.push_back(7);
graf[7].adj.push_back(3);
DFS(1, 1, 0);
HLD(1, 1, 1);
printf("%d\n", LCA(5, 7));
printf("%d\n", LCA(2, 7));
return 0;
}
